﻿// Learn more about F# at http://fsharp.net

open System.Collections.Generic
open System
open System.IO

let flood (board: int[,]) = 
    let n = board.GetLength(0)
    let m = board.GetLength(1)
    let used = Array2D.create n m false

    for i=0 to n-1 do 
        used.[i,0] <- true
        used.[i, m-1] <- true
    for j=0 to m-1 do 
        used.[0, j] <- true
        used.[n-1,j] <- true
    

    let Q = 
        let q = new SortedSet<int*int*int>()
        [
            for i=0 to n-1 do 
                yield board.[i,0], i, 0
                yield board.[i, m-1], i, m-1
            for j=0 to m-1 do 
                yield board.[0, j], 0, j
                yield board.[n-1,j], n-1, j
        ]
        |> List.iter (fun item -> 
            q.Add(item) |> ignore
            )
        q

    let sum = ref 0
    while Q.Count > 0 do 
        let cur = Q.Min
        Q.Remove(Q.Min) |> ignore
        let h, x, y = cur
        [ x+1, y
          x-1, y
          x, y+1 
          x, y-1
        ]
        |> List.filter (fun (x0,y0) -> x0>=0 && x0<n && y0>=0 && y0<m && not used.[x0,y0])
        |> List.iter (fun (x0,y0) ->
            used.[x0,y0] <- true
            if board.[x0,y0] < h then
                //printfn "(%d %d) %d" x0 y0 (h-board.[x0,y0])
                sum := !sum + h - board.[x0,y0]
                Q.Add(h, x0, y0) |> ignore
            else
                Q.Add(board.[x0,y0], x0, y0) |> ignore
            )

    !sum






module Test = 
    let b = 
        [|3; 3; 4; 5; 4; 2;
        3; 1; 3; 2; 1; 3;
        6; 3; 1; 4; 3; 1; |]

    let b2 = Array2D.init 3 6 (fun i j -> b.[i*6+j])


    flood b2

module GenerateOutput = 
    let folder = @"C:\Users\yin\Desktop\local\"
    for i=1 to 13 do 
        let fileName = sprintf "BASEINS.I%d" i
        let text = File.ReadAllText(folder + fileName)
        let s = text.Split([|' '; '\n'; '\r'|], StringSplitOptions.RemoveEmptyEntries)
        let n = int s.[0]
        let m = int s.[1]
        let b = s.[2..(n*m)+1] |> Array.map int
        let b2 = Array2D.init n m (fun i j -> b.[i*m+j])
        let ans = flood b2
        printfn "test %d: %d" i ans
        let outputName = sprintf "BASEINS.O%d" i
        File.WriteAllText(outputName, ans|>string)


